using System;
using System.Collections.Generic;
using UnityEngine;

public static class PointInPolygon
{
    // Define Infinite (Using INT_MAX 
    // caused overflow problems) 
    public static int INF = 10000; 
    
     // Given three colinear points p, q, r, 
    // the function checks if point q lies 
    // on line segment 'pr' 
    public static bool onSegment(Vector2 p, Vector2 q, Vector2 r) 
    { 
        if (q.x <= Math.Max(p.x, r.x) && 
            q.x >= Math.Min(p.x, r.x) && 
            q.y <= Math.Max(p.y, r.y) && 
            q.y >= Math.Min(p.y, r.y)) 
        { 
            return true; 
        } 
        return false; 
    } 
 
    // To find orientation of ordered triplet (p, q, r). 
    // The function returns following values 
    // 0 --> p, q and r are colinear 
    // 1 --> Clockwise 
    // 2 --> Counterclockwise 
    public static int orientation(Vector2 p, Vector2 q, Vector2 r) 
    { 
        float val = (q.y - p.y) * (r.x - q.x) - 
                (q.x - p.x) * (r.y - q.y); 
 
        if (Math.Abs(val) < 0.0001f) 
        {
            return 0; // colinear 
        } 
        return (val > 0) ? 1 : 2; // clock or counterclock wise 
    } 
 
    // The function that returns true if 
    // line segment 'p1q1' and 'p2q2' intersect. 
    public static bool doIntersect(Vector2 p1, Vector2 q1, 
        Vector2 p2, Vector2 q2) 
    { 
        // Find the four orientations needed for 
        // general and special cases 
        int o1 = orientation(p1, q1, p2); 
        int o2 = orientation(p1, q1, q2); 
        int o3 = orientation(p2, q2, p1); 
        int o4 = orientation(p2, q2, q1); 
 
        // General case 
        if (o1 != o2 && o3 != o4) 
        { 
            return true; 
        } 
 
        // Special Cases 
        // p1, q1 and p2 are colinear and 
        // p2 lies on segment p1q1 
        if (o1 == 0 && onSegment(p1, p2, q1)) 
        { 
            return true; 
        } 
 
        // p1, q1 and p2 are colinear and 
        // q2 lies on segment p1q1 
        if (o2 == 0 && onSegment(p1, q2, q1)) 
        { 
            return true; 
        } 
 
        // p2, q2 and p1 are colinear and 
        // p1 lies on segment p2q2 
        if (o3 == 0 && onSegment(p2, p1, q2)) 
        { 
            return true; 
        } 
 
        // p2, q2 and q1 are colinear and 
        // q1 lies on segment p2q2 
        if (o4 == 0 && onSegment(p2, q1, q2)) 
        { 
            return true; 
        } 
 
        // Doesn't fall in any of the above cases 
        return false; 
    } 
 
    // Returns true if the point p lies 
    // inside the polygon[] with n vertices 
    public  static bool isInside(IList<Vector2> polygon, int n, Vector2 p) 
    { 
        // There must be at least 3 vertices in polygon[] 
        if (n < 3) 
        { 
            return false; 
        } 
 
        // Create a point for line segment from p to infinite 
        Vector2 extreme = new Vector2(INF, p.y); 
 
        // Count intersections of the above line 
        // with sides of polygon 
        int count = 0, i = 0; 
        do
        { 
            int next = (i + 1) % n; 
 
            // Check if the line segment from 'p' to 
            // 'extreme' intersects with the line 
            // segment from 'polygon[i]' to 'polygon[next]' 
            if (doIntersect(polygon[i], 
                            polygon[next], p, extreme)) 
            { 
                // If the point 'p' is colinear with line 
                // segment 'i-next', then check if it lies 
                // on segment. If it lies, return true, otherwise false 
                if (orientation(polygon[i], p, polygon[next]) == 0) 
                { 
                    return onSegment(polygon[i], p, 
                                    polygon[next]); 
                } 
                count++; 
            } 
            i = next; 
        } while (i != 0); 
 
        // Return true if count is odd, false otherwise 
        return (count % 2 == 1); // Same as (count%2 == 1) 
    }


    public static void Debug()
    {
        // System.Diagnostics.Stopwatch m_Stopwatch = new System.Diagnostics.Stopwatch();
        //
        // m_Stopwatch.Reset();
        // m_Stopwatch.Start();
        //
        // Vector2 []polygon1 = new Vector2[]
        // {
        //     new Vector2(-1.0f, 0.55f), 
        //     new Vector2(10, 0), 
        //     new Vector2(10, 10), 
        //     new Vector2(-1.0f, 10)
        // };
        // int n = polygon1.Length; 
        // Vector2 p = new Vector2(-0.551f, 0.551f); 
        // for (int i = 0; i < 10000; i++)
        // {
        //
        //     if (isInside(polygon1, n, p)) 
        //     { 
        //         //UnityEngine.Debug.LogError("Yes"); 
        //     } 
        //     else
        //     { 
        //         //UnityEngine.Debug.LogError("No"); 
        //     }
        // }
        //
        //
        // UnityEngine.Debug.LogError("耗时：" + m_Stopwatch.ElapsedMilliseconds); 
        // m_Stopwatch.Stop();
        //
        //
        // p = new Vector2(-1.001f, 5); 
        // if (isInside(polygon1, n, p)) 
        // { 
        //     UnityEngine.Debug.LogError("Yes"); 
        // } 
        // else
        // { 
        //     UnityEngine.Debug.LogError("No"); 
        // } 
        // Vector2 []polygon2 = {new Vector2(0, 0), 
        //     new Vector2(5, 5), 
        //     new Vector2(5, 0)}; 
        // p = new Vector2(3, 3); 
        // n = polygon2.Length; 
        // if (isInside(polygon2, n, p)) 
        // { 
        //     UnityEngine.Debug.LogError("Yes"); 
        // } 
        // else
        // { 
        //     UnityEngine.Debug.LogError("No"); 
        // } 
        // p = new Vector2(5, 1); 
        // if (isInside(polygon2, n, p)) 
        // { 
        //     UnityEngine.Debug.LogError("Yes"); 
        // } 
        // else
        // { 
        //     UnityEngine.Debug.LogError("No"); 
        // } 
        // p = new Vector2(8, 1); 
        // if (isInside(polygon2, n, p)) 
        // { 
        //     UnityEngine.Debug.LogError("Yes"); 
        // } 
        // else
        // { 
        //     UnityEngine.Debug.LogError("No"); 
        // } 
        // Vector2 []polygon3 = {new Vector2(0, 0), 
        //     new Vector2(10, 0), 
        //     new Vector2(10, 10), 
        //     new Vector2(0, 10)}; 
        // p = new Vector2(-1, 10); 
        // n = polygon3.Length; 
        // if (isInside(polygon3, n, p)) 
        // { 
        //     UnityEngine.Debug.LogError("Yes"); 
        // } 
        // else
        // { 
        //     UnityEngine.Debug.LogError("No"); 
        // } 
    }
    
    
}
